package leetcode.dp;

public class matrixMultiply {
    public static void main(String[] args) {

    }
    public static int process(int i,int j,int[] p,int[][] s){
        if (i == j){
            return 0;
        }
        //取第一个断开位置时计算量为初始值
        int m =process(i,j,p,s) + process(i+1,j,p,s)+p[i-1]*p[i]*p[j];
        //记断点为i
        s[i][j] = i;
        for (int k = i+1; k < j; k++) {
            int temp = process(i,k,p,s) + process(k+1,j,p,s)+p[i-1]*p[k]*p[j];
            //取最小的计算量和当前的断点位置
            if (temp<m){
                m = temp;
                s[i][j] = k;
            }
        }
        return m;
    }
}
